It is well known to construct a first-in first-out (FIFO) buffer using counters, adders and combinatorial logic to generate an almost empty and/or an almost full flag. It is also well known to generate the almost empty and almost full flags having a user programmed offset ahead of the respective boundary flags. Typically the almost empty and almost full flags are generated by computing the difference between the write and read counters and comparing this magnitude with the user programmed offset. The read and write counters are reset to zero upon master reset.
In a typical adder/comparator technique, there are two counters one each for the read and write clocks. These two counters are reset to zero upon a master reset and incremented based only on their respective clocks. The outputs of the read and write counters are fed into an adder that calculates the difference between the read and write counters and the magnitude of this difference is then compared with the user programmed offset. The output of the comparator represents the external almost empty flag in the case of asynchronous flags and is the output register data input in the case of synchronous flags. A similar adder comparator pair is used to generate the almost full flag. The main disadvantage with this technique is the long delays associated with generating the almost empty or almost full flag. Additionally, the silicon area requirements are very high because of the requirement of two adder-comparator pairs as well as the complexity of the magnitude comparator. The complexity of the magnitude comparator grows exponentially with the FIFO depth. Filters are typically required that increase the flag delay but are generally required to eliminate any logic hazards at the adder output.
The present invention overcomes the above drawbacks and demonstrates a way to generate almost empty and almost full flags with extremely short delays using minimal silicon area. Additionally, the same logic can be used to generate either the almost empty or the almost full flags. The circuit also provides uniform delay through all the paths and a glitch free output. Linear scalability is one of the added advantages with this invention.